import java.util.ArrayList;

/**
 * 最小的K个数
 * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
 * 
 * 思路：快速排序的方法
 */
public class GetLeastNumbers {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        int size = input.length;
        if (size < k) {
            return new ArrayList<>();
        }
        int left = 0, right = size - 1;
        while (left < right) {
            int part = partition(input, left, right);
            if (part+1 == k) {
                return toList(input, k);
            }
            if (part+1 < k) {
                left = part + 1;
            } else {
                right = part - 1;
            }
        }
        /**
         * 没找到，说明解包含所有元素
         */
        return toList(input, k);
    }

    /**
     * 快速排序经典的分区算法,用左边元素作为枢纽元
     * 使用该函数的前提条件：left < right
     * @param input
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] input, int left, int right) {
        int pivot = input[left];
        int low = left + 1, high = right;
        while (true) {
            /**
            * 找到第一个比pivot小的数
            * 为保证排序稳定性，等于pivot的数不移动
            * 加low < right,保证index不会超出right
            */
            while (pivot >= input[low] && low < right) {
                low++;
            }
            /**
            * 找到第一个比pivot大的数
            * 加high > left,保证high小于枢纽元的index
            */
            while (pivot < input[high] && high > left) {
                high--;
            }
            if (low < high) {
                swap(input, low, high);
            } else {
                break;
            }
        }
        swap(input, left, high);
        return high;
    }

    private void swap(int[] input, int i, int j) {
        int tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;
    }

    private ArrayList<Integer> toList(int[] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        for (int i = 0; i < k; ++i) {
            ret.add(input[i]);
        }
        return ret;
    }
}
